Search results for "Polyhedral combinatorics"
showing 4 items of 4 documents
The project scheduling polyhedron: Dimension, facets and lifting theorems
1993
Abstract The Project scheduling with resource constraints can be formulated as follows: given a graph G with node set N, a set H of directed arcs corresponding to precedence relations, and a set H′ of disjunctive arcs reflecting the resource incompatibilities, find among the subsets of H′ satisfying the resource constraints the set S that minimizes the longest path in graph (N, H ∪ S). We define the project scheduling polyhedron Qs as the convex hull of the feasible solutions. We investigate several classes of inequalities with respect to their facet-defining properties for the associated polyhedron. The dimension of Qs is calculated and several inequalities are shown to define facets. For …
The mixed general routing polyhedron
2003
[EN] In Arc Routing Problems, ARPs, the aim is to find on a graph a minimum cost traversal satisfying some conditions related to the links of the graph. Due to restrictions to traverse some streets in a specified way, most applications of ARPs must be modeled with a mixed graph. Although several exact algorithms have been proposed, no polyhedral investigations have been done for ARPs on a mixed graph. In this paper we deal with the Mixed General Routing Problem which consists of finding a minimum cost traversal of a given link subset and a given vertex subset of a mixed graph. A formulation is given that uses only one variable for each link (edge or arc) of the graph. Some properties of the…
New Results on the Mixed General Routing Problem
2005
[EN] In this paper, we deal with the polyhedral description and the resolution of the Mixed General Routing Problem. This problem, in which the service activity occurs both at some of the nodes and at some of the arcs and edges of a mixed graph, contains a large number of important arc and node routing problems as special cases. Here, a large family of facet-defining inequalities, the Honeycomb inequalities, is described. Furthermore, a cutting-plane algorithm for this problem that incorporates new separation procedures for the K-C, Regular Path-Bridge, and Honeycomb inequalities is presented. Branch and bound is invoked when the final solution of the cutting-plane procedure is fractional. …
Formulations and valid inequalities for the capacitated dispersion problem
2023
This work focuses on the capacitated dispersion problem for which we study several mathematical formulations in different spaces using variables associated with nodes, edges, and costs. The relationships among the presented formulations are investigated by comparing the projections of the feasible sets of the LP relaxations onto the subspace of natural variables. These formulations are then strengthened with families of valid inequalities and variable-fixing procedures. The separation problems associated with the valid inequalities that are exponential in number are shown to be polynomially solvable by reducing them to longest path problems in acyclic graphs. The dual bounds obtained from s…